/**
 * @Project : algorithm-learning
 * @Author : Ruoyu Wang
 * @User : Momenta
 * @DateTime : 2024/3/20 18:50
 */

//帅帅经常跟同学玩一个矩阵取数游戏：对于一个给定的 n*m 的矩阵，矩阵中的每个元素aij均为非负整数。游戏规则如下：
//1.每次取数时须从每行各取走一个元素，共 n 个。m 次后取完矩阵所有元素；
//2.每次取走的各个元素只能是该元素所在行的行首或行尾；
//3.每次取数都有一个得分值，为每行取数的得分之和，每行取数的得分 = 被取走的元素值 * 2^i，其中i表示第i次取数（从1开始编号）；
//4.游戏结束总得分为 m 次取数得分之和。
//帅帅想请你帮忙写一个程序，对于任意矩阵，可以求出取数后的最大得分。
//
//数据范围1<= n,m <=100，
//矩阵中的值满足1<= val <=1000
//由于得分可能会非常大，所以把值对10^9+7取模
//
//示例 1
//输入
//[[1,2,3],[3,4,2]]
//输出
//82
//说明
//  第1次：第1行取行首元素，第2行取行尾元素，本次得分为1 * 21 + 2 * 21 = 6
//  第2次：两行均取行首元素，本次得分为2 * 22 + 3 * 22 = 20
//  第3次：得分为3 * 23 + 4 * 23 = 56。
//  总得分为6 + 20 + 56 = 82
//
//示例 2
//输入
//[[4,5,0,5]]
//输出
//122
//
//示例 3
//输入
//[[96,56,54,46,86,12,23,88,80,43],[16,95,18,29,30,53,88,83,64,67]]
//输出
//316994

#include <iostream>
#include <vector>

using namespace std;

const int MOD = 1000000007;

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param matrix int整型vector<vector<>>
     * @return int整型
     */
    int matrixScore(vector<vector<int>> &matrix) {
        int op[matrix.size()][2];
        for (int i = 0; i < matrix.size(); ++i) {
            op[i][0] = 0;
            op[i][1] = matrix[0].size() - 1;
        }
        long long res = 0;
        long long a = 1;
        for (int i = 0; i < matrix[0].size(); ++i) {
            long long sum = 0;
            for (int j = 0; j < matrix.size(); ++j) {
                if (matrix[j][op[j][0]] > matrix[j][op[j][1]]) {
                    sum += matrix[j][op[j][1]];
                    op[j][1]--;
                } else {
                    sum += matrix[j][op[j][0]];
                    op[j][0]++;
                }
            }
            cout << endl;
            a = (a * 2) % MOD;
            res = (res + sum * a) % MOD;
        }
        return (int) res;
    }
};

using namespace std;

int main() {
    Solution sl;
    vector<vector<int>> matrix = {{96, 56, 54, 46, 86, 12, 23, 88, 80, 43},
                                  {16, 95, 18, 29, 30, 53, 88, 83, 64, 67}};
    printf("%d", sl.matrixScore(matrix));
    //316994
//    printf("%d", sl.quickMi(2,20));
    return 0;
}